// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <cstdio>
#include <vector>

void scan(int & a)
{
	a = 0;
	bool flag = false;
	char ch = std::getchar();
	if (ch == '-')
		flag = true;
	else if (ch >= '0' && ch <= '9')
		a = ch - '0';

	while ((ch = std::getchar()) >= '0' && ch <= '9')
		a = a * 10 + ch - '0';
	if (flag) a = -a;
}

int const maxn = 10007;
int const maxm = 600;
int to_root[maxn];
int a[maxn];
int n, ans;

std::vector<int> tree[maxn];
std::vector<int> all[maxm];

int dp[4 * maxn][50];  //这个数组记得开到2*maxn，因为遍历后序列长度为2*n-1
bool vis[maxn];
int tot;

int ver[4*maxn],R[4*maxn],first[maxn],dir[maxn];
//ver:节点编号 R：深度 first：点编号位置 dir：距离

void dfs_seq(int u, int fa, int dep)
{
	vis[u] = true; ver[++tot] = u; first[u] = tot; R[tot] = dep;
	for (int i = 0; i < (int)tree[u].size(); i++) {
		int v = tree[u][i];
		if (v == fa) continue;
		dir[v] = dir[u] + 1;
		dfs_seq(v, u, dep + 1);
		ver[++tot] = u; R[tot] = dep;
	}
}

void ST(int n)
{
	for(int i=1;i<=n;i++) dp[i][0] = i;
	for(int j=1;(1<<j)<=n;j++) {
		for(int i=1;i+(1<<j)-1<=n;i++) {
			int a = dp[i][j-1] , b = dp[i+(1<<(j-1))][j-1];
			dp[i][j] = R[a]<R[b]?a:b;
		}
	}
}
//中间部分是交叉的。
int RMQ(int l,int r)
{
	int k=0;
	while((1<<(k+1))<=r-l+1)
		k++;
	int a = dp[l][k], b = dp[r-(1<<k)+1][k]; //保存的是编号
	return R[a]<R[b]?a:b;
}

int lca(int u ,int v)
{
	//printf("%d %d\n", u, v);
	int x = first[u] , y = first[v];
	if(x > y) std::swap(x,y);
	int res = RMQ(x,y);
	return ver[res];
}

void add_edge(int x, int y)
{
	tree[x].push_back(y);
	tree[y].push_back(x);
}

int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }

void dfs(int u, int fa, int dis)
{
	to_root[u] = dis;
	for (int i = 0; i < (int)tree[u].size(); i++) {
		int v = tree[u][i];
		if (v == fa) continue;
		dfs(v, u, dis + 1);
	}
}

int main()
{
	scan(n);
	int max = 0, min = 600;
	for (int i = 1; i <= n; i++) {
		scan(a[i]);
		all[a[i]].push_back(i);
		max = std::max(max, a[i]);
		min = std::min(min, a[i]);
	}
	for (int i = 1, x, y; i < n; i++) {
		scan(x); scan(y);
		add_edge(x, y);
	}
	dfs(1, -1, 0);
	tot = 0; dir[1] = 0;
	dfs_seq(1, -1, 0);
	ST(2 * n - 1);
	for (int i = min; i <= max; i++) {
		if (!all[i].size()) continue;
		for (int j = i; j <= max; j++) {
			if (!all[j].size()) continue;
			if (gcd(i, j) != 1) continue;
			for (int l1 = 0; l1 < (int)all[i].size(); l1++)
				for (int l2 = 0; l2 < (int)all[j].size(); l2++) {
					int cr = lca(all[i][l1], all[j][l2]);
//					std::cerr << all[i][l1] << ' ' << all[j][l2] << ' ' << cr << ' ' << to_root[all[i][l1]] + to_root[all[j][l2]] - 2 * to_root[cr] << '\n';
					ans += to_root[all[i][l1]] + to_root[all[j][l2]] - 2 * to_root[cr];
				}
		}
	}
	printf("%d\n", ans);
}

